Recherche d’une route dans un réseau

TP n° 10

Recherche d’une route dans un réseau(2)

On désire écrire une petite application pour permettre de trouver le chemin à utiliser pour aller d’une station à une autre dans le métro de Paris (pour celui de Rennes c’est trop facile).

On réalisera cette application en deux phases :

Construction d’une représentation en mémoire du réseau (le TP précédent),

Recherche d’un chemin dans ce réseau (ce TP).

On appellera station multiple une station qui se trouve sur plusieurs lignes de métro et permet donc de faire l’interconnexion de ces lignes.

Modification des fichiers

On a rajouté dans le répertoire /home-info/commun/3info/LangageC/TP10 :

Le fichier Chemin.h,

Le squelette de Chemin.c,

La mise à jour du répertoire DOC, consultable au moyen de votre navigateur qui donne les informations sur chacun des modules composant cette application. Pour cela afficher la page : /home-info/commun/3info/LangageC/TP10/DOC/files.html

Modification des fichiers

Modifier votre makefile pour qu’il intègre le nouveau module Chemin.c. Vous pouvez maintenant utiliser make dep, car makedepend a été installé dans votre environnement.

Retirer également le commentaire dans le main et dans la fonction Res_router.

Par la suite vous pourrez être conduit à définir et à insérer de nouvelles fonctions dans les modules réalisés lors de la première partie.

Phase 2 : Trouver les chemins issus d'un sommet :

La recherche des plus courts chemins issus d’un sommet peut se faire par l’algorithme de Djikstra. La description ci-dessous provient du site Interstice. Sur ce site il y a également une animation qui permet de comprendre le fonctionnement cet algorithme. Pour trouver ce site le plus simple est de faire une recherche sur Google avec 'Interstices court chemin'.

Objectif 1 : comprendre l’algorithme

Pour chaque sommet x, on veut calculer la valeur minimum m(x) des chemins allant du sommet de départ A vers x. Pour le routage, on veut déterminer le prédécesseur de x, noté p(x), sur un chemin de valeur m(x). Ceci permet de tracer, en le remontant, le meilleur chemin du sommet de départ A vers n'importe quel sommet x.

L'algorithme de Dijkstra repose sur le principe d'exploration à partir du meilleur, c'est à dire du meilleur prédécesseur visité.

Un sommet x est dit visité si au moins un chemin de A vers x a été évalué ; un sommet visité possède des valeurs m(x), p(x) provisoires : m(x) est la valeur minimum des chemins de A vers x déjà évalués, et p(x) le prédécesseur correspondant.

Un sommet est dit calculé s'il est visité et si l'on sait que ses valeurs m(x), p(x) sont définitives (et correctes).

Initialement, bien sûr, le sommet A est calculé (avec m(A) = 0, p(A) non défini puisque A est le point de départ des chemins), et chaque successeur x de A est visité, avec m(x) = v(A, x), p(x) = A.

Le principe d'exploration à partir du meilleur consiste à chercher, parmi les sommets visités non encore calculés, un sommet dont la valeur m(x) est minimum. On peut alors démontrer que, pour un tel sommet, les valeurs provisoires m(x), p(x) sont définitives (et correctes). Cette démonstration utilise explicitement le fait que les valeurs sont non négatives.

On marque donc x comme calculé et on prolonge l'exploration en examinant chacun des successeurs de x : chaque successeur y non encore visité devient visité, avec m(y) = m(x) + v(y, x), p(y) = x tandis que, pour chaque successeur y déjà visité, on effectue la mise à jour m(y) = min(m(y), m(x) + v(x, y)) (et p(y) = p(x) si m(y) est mis à jour). L'exploration s'arrête lorsque tous les sommets visités sont calculés (les sommets non visités sont inaccessibles, on peut considérer qu'ils ont une valeur m(x) = +∞).

Par rapport à cette description et au texte donné sur le site, on remarque qu’on peut simplifier l’initialisation en mettant le sommet A dans provisoires et non dans calculés.

La complexité de l'algorithme est de l’ordre de n².

Objectif 2 : réaliser des fonctions de service

Pour s’adapter à cet algorithme, on représente un sommet x par la structure Etape contenant :

un pointeur vers une station,

un index dans l’ensemble des sommets calculés pour retrouver le prédécesseur p(x),

la distance m(x).

Pour représenter un ensemble tel que calculés ou provisoires on utilise la structure Chemin qui contient le nombre d’éléments et un pointeur vers un tableau d’Etape.

Commencer par écrire les fonctions de service : Chem_existe, Chem_meilleur, Chem_ajouter, Chem_retirer, Chem_print.

Objectif 3 : réaliser le cœur de l’algorithme

Comment, en fonction du nombre de stations d’un réseau, faut-il dimensionner la taille du tableau des étapes associé à une structure Chemin ?

Si vous avez bien retiré les commentaires dans le main et dans Res_router, vous pouvez facilement tester la génération de tous les chemins qui partent de la première station par ordre alphabétique.

Dans Chem_construire créer les structures pour la gestion des ensembles calculés et provisoires.

Initialiser provisoires avec la station depart passée en paramètre.

Ce début doit vous permettre de tester un bon nombre des fonctions de service.

Ecrire la fonction Chem_candidat qui réalise le cas à l’intérieur de la boucle pour tout sommet y successeur de x

Réfléchir à la manière de générer l’ensemble des successeurs d’une station au moyen des fonctions Sta_nextLigne et Sta_nextNom.

Faire la boucle générale tant que provisoire non vide. En sortie de boucle, ne pas oublier de libérer les allocations de  mémoire.

Pour tester on pourra mettre des impressions intermédiaires grace à Chem_print.

Faire un premier test avec une seule ligne.

On pourra ensuite tester avec 2 lignes, et puis supprimer les impressions intermédiaires et tester sur tout le réseau.

Prévoir une extension rudimentaire de Res_router qui se limite à lire au clavier 2 numéros pour choisir les stations.

Ceux qui sont à l’aise, pourront montrer que l’on peut utiliser 2 fois moins de mémoire en faisant partager un même tableau d’Etape par les ensembles calculés et provisoires. Ceci nécessite toutefois de reprendre la programmation de Chem_retirer.

Objectif 4 : s’adapter aux besoins

Sachant que pour désigner une station, un utilisateur ne précisera pas la ligne mais se servira uniquement du nom, modifier l’algorithme (initialisation et test de fin).

Réaliser la fonction Chem_trajet, qui affiche dans le bon ordre les stations traversées. On pourra en faire une version simple, toutes les stations ; une version plus facile à lire, sans les stations intermédiaires entre deux stations multiples ; ou finalement complète en indiquant la ligne à prendre et le nom de la direction (nom du terminus).

Objectif 5 : définir l’interface utilisateur

L’interface pour sélectionner un élément dans un grand nombre (ici 346 stations) n’est pas très simple à concevoir. La solution rudimentaire avec saisie d’un numéro est à exclure, la frappe du nom en entier est trop sensible aux erreurs de frappe.

Imaginer une solution s’inspirant vaguement des expressions régulières dans laquelle on pourrait s’appuyer sur les lettres en majuscule et réaliser des impressions partielles des noms ainsi sélectionnés. Vous pouvez également proposer une autre approche.

Objectif 5 : générer la documentation

Appeler doxygen –s metro.doxy pour créer le fichier de configuration par défaut.

Dans metro.doxy mettre à jour les lignes PROJECT_NAME, OUTPUT_LANGUAGE, OPTIMIZE_OUTPUT_FOR_C, FILE_PATTERNS, HTML_OUTPUT = DOC, GENERATE_LATEX = NO, HAVE_DOT=YES

Rappeler doxygen metro.doxy et utiliser votre navigateur pour voir la documentation.